﻿//#define dowhile
#define swapper

using System;
using System.Linq;
using System.Diagnostics;
using System.Runtime.InteropServices;
using System.Threading;
using System.Collections.Generic;

namespace alib.Array
{
	using SysArray = System.Array;

	public class IntArrayEqualityComparer : IEqualityComparer<int[]>
	{
		public static readonly IntArrayEqualityComparer Default = new IntArrayEqualityComparer();
		private IntArrayEqualityComparer() { }

		public bool Equals(int[] x, int[] y)
		{
			if (x == null && y == null)
				return true;
			if (x == null || y == null)
				return false;
			if (x.Length != y.Length)
				return false;
			for (int i = 0; i < x.Length; i++)
				if (x[i] != y[i])
					return false;
			return true;
		}

		public int GetHashCode(int[] obj)
		{
			if (obj == null || obj.Length == 0)
				return 0;
			var hashCode = 0;
			for (var i = 0; i < obj.Length; i++)
				// Rotate by 3 bits and XOR the new value. 
				hashCode = (hashCode << 3) | (hashCode >> (29)) ^ obj[i];
			return hashCode;
		}
	};

	[DebuggerDisplay("{ToString(),nq}")]
	public struct HashArray : IEquatable<HashArray>
	{
		readonly int[] arr;
		int hash;

		public HashArray(IEnumerable<int> hashes)
		{
			this.arr = hashes as int[] ?? hashes.ToArray();
			this.hash = arr.Length;
			if (arr.Length > 1)
				SysArray.Sort(arr);
		}

		public override string ToString()
		{
			return Enumerable._enumerable_ext.StringJoin(arr, "-");
		}

		public override int GetHashCode()
		{
			if (hash == arr.Length)
			{
				int v, j = 8;
				for (int i = 0; i < arr.Length; )
				{
					hash ^= ((v = arr[i++]) << i) | (v >> (32 - i));
					if ((j += 4) >= 31)
						j = 0;
				}
			}
			return hash;
		}

		public bool Equals(HashArray other)
		{
			if (this.GetHashCode() != other.GetHashCode())
			{
				Debugging.Nop.CodeCoverage();
				return false;
			}
			for (int i = 0; i < arr.Length; i++)
				if (arr[i] != other.arr[i])
				{
					Debugging.Nop.CodeCoverage();
					return false;
				}
			return true;
		}

		public override bool Equals(object obj)
		{
			return obj is HashArray && this.Equals((HashArray)obj);
		}
	};

	public struct ObjectHashArray<T> : IList<T>, IEquatable<ObjectHashArray<T>> where T : class, IComparable<T>
	{
		readonly T[] arr;
		int hash;

		public ObjectHashArray(IEnumerable<T> hashes)
		{
			this.arr = hashes as T[] ?? hashes.ToArray();
			this.hash = arr.Length;
			if (arr.Length > 1)
				SysArray.Sort(arr);
		}

		public override int GetHashCode()
		{
			if (hash == arr.Length)
			{
				int v, j = 8;
				for (int i = 0; i < arr.Length; )
				{
					hash ^= ((v = arr[i++].GetHashCode()) << j) | (v >> (32 - j));
					if ((j += 4) >= 31)
						j = 0;
				}
			}
			return hash;
		}

		public bool Equals(ObjectHashArray<T> other)
		{
			if (this.GetHashCode() != other.GetHashCode())
			{
				Debugging.Nop.CodeCoverage();
				return false;
			}
			for (int i = 0; i < arr.Length; i++)
				if (!Object.Equals(arr[i], other.arr[i]))
				{
					Debugging.Nop.CodeCoverage();
					return false;
				}
			return true;
		}

		public override bool Equals(object obj)
		{
			return obj is ObjectHashArray<T> && this.Equals((ObjectHashArray<T>)obj);
		}

		public T this[int index]
		{
			get { return arr[index]; }
			set { throw new InvalidOperationException(); }
		}

		public int IndexOf(T item) { return SysArray.IndexOf<T>(arr, item); }
		public bool Contains(T item) { return SysArray.IndexOf<T>(arr, item) != -1; }
		public void CopyTo(T[] array, int arrayIndex) { arr.CopyTo(array, arrayIndex); }

		public int Count { get { return arr.Length; } }
		public bool IsReadOnly { get { return true; } }

		public void Insert(int index, T item) { throw new InvalidOperationException(); }
		public void RemoveAt(int index) { throw new InvalidOperationException(); }
		public void Add(T item) { throw new InvalidOperationException(); }
		public void Clear() { throw new InvalidOperationException(); }
		public bool Remove(T item) { throw new InvalidOperationException(); }

		public IEnumerator<T> GetEnumerator()
		{
			return ((IEnumerable<T>)arr).GetEnumerator();
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return arr.GetEnumerator();
		}
	};

	public static class arr
	{
		/// <summary>
		/// You can use this extension method on a null 'this' value (i.e. properly-typed).
		/// A single-element array is returned. This function is thread-safe.
		/// </summary>
		public static T[] Append<T>(this T[] src, T item)
		{
			T[] dst;
			int c = src == null ? 0 : src.Length;
			(dst = new T[c + 1])[c] = item;
			while (--c >= 0)
				dst[c] = src[c];
			return dst;
		}
		public static int Append<T>(ref T[] src, T item)
		{
			int c;
			T[] _new, _tmp = src;
			do
			{
				(_new = new T[(c = _tmp == null ? 0 : _tmp.Length) + 1])[c] = item;
				while (--c >= 0)
					_new[c] = _tmp[c];
			}
			while (_tmp != (_tmp = Interlocked.CompareExchange(ref src, _new, _tmp)));
			return _new.Length - 1;
		}

		/// <summary>
		/// Doesn't check for duplicates
		/// </summary>
		public static void AppendSafe<T>(ref T[] rgh, T t)
		{
			T[] _cur;
			if ((_cur = rgh ?? Interlocked.CompareExchange(ref rgh, new[] { t }, null)) != null)
				while (_cur != (_cur = Interlocked.CompareExchange(ref rgh, Append(_cur, t), _cur)))
					;
		}

		public static T[] AppendSafeIfNotNull<T>(ref T[] rgh, T t)
		{
			T[] _cur = rgh, _new;
			do
				if (_cur == null)
					return null;
			while (_cur != (_cur = Interlocked.CompareExchange(ref rgh, _new = Append(_cur, t), _cur)));
			return _new;
		}

		/// <summary>
		/// You can use this extension method on a null 'this' value (i.e. properly-typed).
		/// A single-element array is returned. This function is thread-safe.
		/// </summary>
		public static T[] Prepend<T>(this T[] src, T item)
		{
			T[] dst;
			int c = src == null ? 0 : src.Length;
			(dst = new T[c + 1])[0] = item;
			while (c > 0)
				dst[c] = src[--c];
			return dst;
		}
		public static T[] Resize<T>(T[] src, int c)
		{
			if (c == 0)
				return Collections.Collection<T>.None;

			if (src == null)
				return new T[c];

			int cc;
			if ((cc = src.Length) == c)
				return src;

			T[] tmp = new T[c];
			if (cc < c)
				c = cc;
			while (--c >= 0)
				tmp[c] = src[c];
			return tmp;
		}

		public static void Resize<T>(ref T[] arr, int c) { arr = Resize(arr, c); }

		public static T[][] Divide<T>(this T[] src, int count)
		{
			if (count == 0)
				throw new Exception();

			int i, j, k, m;
			j = k = src.Length / count;
			if ((m = src.Length % count) != 0)
				j++;
			var ret = new T[j][];
			for (i = 0, j = 0; i < k; i++, j += count)
				SysArray.Copy(src, j, ret[i] = new T[count], 0, count);
			if (m != 0)
				SysArray.Copy(src, j, ret[i] = new T[m], 0, m);
			return ret;
		}

		/// <summary>
		/// You can use this extension method on a null 'this' value (i.e. properly-typed).
		/// The 'more' array (or Collection(T).None if null) is returned in this case.
		/// </summary>
		public static T[] Concat<T>(this T[] src, T[] more)
		{
			int c_src, c_more;
			if (more == null || (c_more = more.Length) == 0)
				return src ?? Collections.Collection<T>.None;

			if (src == null || (c_src = src.Length) == 0)
				return more ?? Collections.Collection<T>.None;

			T[] dst = new T[c_src + c_more];
			int i = 0;
			for (; i < c_src; i++)
				dst[i] = src[i];

			for (int j = 0; j < c_more; j++)
				dst[i++] = more[j];
			return dst;
		}

		public static void FilterFor<TArr, TFilter>(ref TArr[] arr)
			where TArr : class
			where TFilter : class,TArr
		{
			int c = arr.Length;
			if (c > 0)
			{
				int j = 0;
				for (int i = 0; i < c; i++)
					if (!(arr[i] is TFilter))
						j++;
				if (j > 0)
				{
					TFilter[] dst = new TFilter[c - j];
					TFilter t;
					j = 0;
					for (int i = 0; i < c; i++)
						if ((t = (arr[i] as TFilter)) != null)
							dst[j++] = t;
					arr = dst;
				}
			}
		}

		public static int IndexofAny<T>(this T[] arr, T[] items)
		{
			int ci;
			if ((ci = items.Length) > 0 && arr.Length > 0)
			{
				if (ci == 1)
					return System.Array.IndexOf(arr, items[0]);

				for (int i = 0; i < arr.Length; i++)
					if (System.Array.IndexOf<T>(items, arr[i]) != -1)
						return i;
			}
			return -1;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// remember to re-store the return value of this extension
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static void RemoveAt<T>(ref T[] arr, int idx)
		{
			arr = RemoveAt(arr, idx);
		}
		public static T[] RemoveAt<T>(this T[] arr, int idx)
		{
			int c = arr.Length;
			if (idx < 0 || idx >= c)
				throw new IndexOutOfRangeException();

			T[] newarr = new T[c - 1];

			SysArray.Copy(arr, 0, newarr, 0, idx);					// part I.

			int i_src = idx + 1;
			SysArray.Copy(arr, i_src, newarr, idx, c - i_src);		// part II.

			return newarr;
		}
		public static bool Remove<T>(ref T[] arr, T t)
		{
			int c = arr.Length;
			for (int i = 0; i < c; i++)
				if (arr[i].Equals(t))
				{
					arr = RemoveAt(arr, i);
					return true;
				}
			return false;
		}
		public static T[] Remove<T>(this T[] arr, T t)
		{
			int c = arr.Length;
			for (int i = 0; i < c; i++)
				if (arr[i].Equals(t))
					return RemoveAt(arr, i);
			throw new Exception();
		}
		public static void RemoveSafe<T>(ref T[] arr, T t)
		{
			T[] _tmp;
			if ((_tmp = arr) != null)
				while (_tmp != (_tmp = Interlocked.CompareExchange(ref arr, remove_all(_tmp, t), _tmp)))
					;
		}

		static T[] remove_all<T>(T[] arr, T t)
		{
			T[] _rep = null;
			int c, i, j;
			if ((c = arr.Length - 1) >= 0)
			{
				i = j = 0;
				if (c > 0)
					for (; i < c; i++)
						if (!arr[i].Equals(t))
							(_rep ?? (_rep = new T[c]))[j++] = arr[i];

				if (!arr[i].Equals(t))
				{
					if (i == j)
						return arr;
					(_rep = Resize(_rep, ++j))[j - 1] = arr[i];
				}
				else if (j > 0 && j < c)
					_rep = Resize(_rep, j);
			}
			return _rep;
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// remember to re-store the return value of this extension
		/// Array.Resize always copies to a new array. Rather than sliding the original array and doing a 
		/// resize, we'll just create the new array ourselves and avoid Array.Resize.
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static T[] RemoveRange<T>(this T[] arr, int ix, int count)
		{
			int _arr, ix_resume;

			if (ix < 0 || ix >= (_arr = arr.Length))
				throw new IndexOutOfRangeException();
			if (count == 0)
				return arr;
			if (count < 0 || (ix_resume = ix + count) > _arr)
				throw new ArgumentOutOfRangeException();
			if ((count = _arr - count) == 0)
				return alib.Collections.Collection<T>.None;

			T[] newarr = new T[count];

			count = 0;
			while (count < ix)
				newarr[count] = arr[count++];

			while (ix_resume < _arr)
				newarr[count++] = arr[ix_resume++];

			return newarr;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static bool ValueCompare<T>(this T[] a, T[] b) where T : struct
		{
			if (a.Length != b.Length)
				return false;

			EqualityComparer<T> q = EqualityComparer<T>.Default;
			for (int i = 0; i < a.Length; i++)
				if (!q.Equals(a[i], b[i]))
					return false;

			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static bool ValueCompare<T>(this T[] a, int a_offset, T[] b) where T : struct
		{
			if (a_offset >= a.Length || a_offset + b.Length > a.Length)
				return false;

			EqualityComparer<T> q = EqualityComparer<T>.Default;
			for (int i = 0; i < b.Length; i++, a_offset++)
				if (!q.Equals(a[a_offset], b[i]))
					return false;

			return true;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// In a list of objects of type T which are sorted in order based on type K, search for a value of type K.
		/// </summary>
		/// <remarks>
		/// http://www.removingalldoubt.com/permalink.aspx/f7e6feff-8257-4efe-ad64-acd1c7a4a1e3
		/// </remarks>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static int BinarySearch<T, K>(this IList<T> list, K value, Converter<T, K> convert, Comparison<K> compare)
		{
			int i = 0;
			int j = list.Count - 1;
			while (i <= j)
			{
				int m = i + (j - i) / 2;
				int r = compare(convert(list[m]), value);
				if (r == 0)
					return m;
				if (r < 0)
					i = m + 1;
				else
					j = m - 1;
			}
			return ~i;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// In a list of objects of type T which are sorted an order based on type K, search for a value of type K.
		/// </summary>
		/// <typeparam name="T">Type the objects in the list</typeparam>
		/// <typeparam name="K">Type of the key by by which the objects in the list are sorted</typeparam>
		/// <param name="list">IList interface handle to a list of objects of type T</param>
		/// <param name="item">Object of type K to search for</param>
		/// <param name="convert">Function which derives a key of type K from an object of type T</param>
		/// <returns>
		/// The zero-based index of the item in the list if it is found; otherwise, a negative number that is 
		/// the bitwise complement of the index of the next element that is larger than item
		/// </returns>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static int BinarySearch<T, K>(this IList<T> list, K item, Converter<T, K> convert)
			where K : IComparable<K>
		{
			return BinarySearch<T, K>(list, item, list.Count, convert);
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// Among the first 'c' elements of a list of objects of type T which are sorted an order based on type K, 
		/// search for a value of type K.
		/// </summary>
		/// <typeparam name="T">Type the objects in the list</typeparam>
		/// <typeparam name="K">Type of the key by by which the objects in the list are sorted</typeparam>
		/// <param name="list">IList interface handle to a list of objects of type T</param>
		/// <param name="item">Object of type K to search for</param>
		/// <param name="c">Number of objects at the beginning of the list to search within</param>
		/// <param name="convert">Function which derives a key of type K from an object of type T</param>
		/// <returns>
		/// The zero-based index of the item in the list if it is found; otherwise, a negative number that is 
		/// the bitwise complement of the index of the next element that is larger than item
		/// </returns>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static int BinarySearch<T, K>(this IList<T> list, K item, int c, Converter<T, K> convert)
			where K : IComparable<K>
		{
			int i = 0;
			int j = c - 1;
			while (i <= j)
			{
				int m = i + (j - i) / 2;
				int r = convert(list[m]).CompareTo(item);
				if (r == 0)
					return m;
				if (r < 0)
					i = m + 1;
				else
					j = m - 1;
			}
			return ~i;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// 
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public static void Swap<T>(this IList<T> rg, int i_l, int i_r)
		{
			if (i_l != i_r)
			{
				T _tmp = rg[i_r];
				rg[i_r] = rg[i_l];
				rg[i_l] = _tmp;
			}
		}
		public static void Swap<T>(this T[] rg, int a, int b)
		{
			if (a != b)
			{
				T _tmp = rg[b];
				rg[b] = rg[a];
				rg[a] = _tmp;
			}
		}

		[ThreadStatic]
		static Random rnd;

		public static void Shuffle<T>(this T[] arr)
		{
			if (rnd == null)
				rnd = new Random();
			int r, c = arr.Length;
			for (int i = 0; i < c; i++)
				if ((r = rnd.Next(c)) != i)
					alib.Enumerable._enumerable_ext.Swap<T>(ref arr[i], ref arr[r]);
		}

		public static bool IsSorted<T>(this T[] arr, IComparer<T> cmp)
		{
			int c = arr.Length;
			if (c >= 2)
			{
				T item = arr[0];
				for (int i = 1; i < c; i++)
					if (cmp.Compare(item, item = arr[i]) > 0)
						return false;
			}
			return true;
		}

		public static bool IsSorted<T>(this T[] arr, int c, IComparer<T> cmp)
		{
			if (c >= 2)
			{
				T item = arr[0];
				for (int i = 1; i < c; i++)
					if (cmp.Compare(item, item = arr[i]) > 0)
						return false;
			}
			return true;
		}


		public static bool IsSorted<T>(this T[] arr, int i, int count, IComparer<T> cmp)
		{
			if (count > 1)
			{
				count += i;
				T i_prev = arr[i++];
				while (i < count)
					if (cmp.Compare(i_prev, i_prev = arr[i++]) > 0)
						return false;
			}
			return true;
		}

		public static void qsort<T>(this T[] rg, IComparer<T> cmp) where T : class
		{
			if (rg.Length > 1)
				qsort<T>(rg, 0, rg.Length - 1, cmp);
		}

		//static void swap_if<T>(T[] keys, IComparer<T> comparer, int a, int b)
		//{
		//	if (a != b && comparer.Compare(keys[a], keys[b]) > 0x0)
		//	{
		//		T tmp = keys[a];
		//		keys[a] = keys[b];
		//		keys[b] = tmp;
		//	}
		//}
#if true

		struct swap_help<T>
		{
			public IComparer<T> comparer;

			public void cmp_swap(ref T x, ref T y)
			{
				T tmp;
				if (comparer.Compare(tmp = x, y) != 0)
				{
					x = y;
					y = tmp;
				}
			}

			public void go(int f, int g, ref T a, ref T b, ref T c)
			{
				if (f != 0)
					cmp_swap(ref a, ref c);

				if (f != g)
					cmp_swap(ref a, ref b);

				if (0 != g)
					cmp_swap(ref c, ref b);
			}
		};

		static void swapper<T>(T[] keys, IComparer<T> comparer, int a, int b, int c)
		{
			swap_help<T> sh;
			sh.comparer = comparer;
			sh.go(a ^ c, c ^ b, ref keys[a], ref keys[b], ref keys[c]);
		}

#else
		static void swapper<T>(T[] keys, IComparer<T> comparer, int a, int b, int c)
		{
			T x, y;
			if (a != c && comparer.Compare(x = keys[a], y = keys[c]) > 0x0)
			{
				keys[a] = y;
				keys[c] = x;
			}

			if (a != b && comparer.Compare(x = keys[a], y = keys[b]) > 0x0)
			{
				keys[a] = y;
				keys[b] = x;
			}

			if (c != b && comparer.Compare(x = keys[c], y = keys[b]) > 0x0)
			{
				keys[c] = y;
				keys[b] = x;
			}
		}
#endif
		public static void qsort<T>(this T[] arr, int left, int right, IComparer<T> cmp) //where T : class
		{
			do
			{
				int a = left, b = right, mid = a + ((b - a) >> 0x1);
#if swapper
				swapper(arr, cmp, a, b, mid);
#else
				swap_if(keys, cmp, a, mid);
				swap_if(keys, cmp, a, b);
				swap_if(keys, cmp, mid, b);
#endif
				T y = arr[mid];
				do
				{
					T ta;
					while (!(ta = arr[a]).Equals(y) && cmp.Compare(ta, y) < 0x0)
						a++;
					T tb = a == b ? ta : arr[b];
					while (!tb.Equals(y) && cmp.Compare(y, tb) < 0x0)
						tb = arr[--b];

					if (a > b)
						break;
					if (a < b)
					{
						arr[a] = tb;
						arr[b] = ta;
					}
					a++;
					b--;
				}
				while (a <= b);

				if ((b - left) <= (right - a))
				{
					if (left < b)
						qsort(arr, left, b, cmp);
					left = a;
				}
				else
				{
					if (a < right)
						qsort(arr, a, right, cmp);
					right = b;
				}
			}
			while (left < right);
		}

		static unsafe void swapper(IntPtr* keys, IComparer<IntPtr> comparer, int a, int b, int q)
		{
			IntPtr ta = IntPtr.Zero, tb = IntPtr.Zero, tq = IntPtr.Zero;
			if (a != q && comparer.Compare(ta = keys[a], tq = keys[q]) > 0x0)
			{
				keys[a] = tq;
				keys[q] = ta;
				ta = tq = default(IntPtr);
			}
			if (a != b && comparer.Compare(ta = ta != IntPtr.Zero ? ta : keys[a], tb = keys[b]) > 0x0)
			{
				keys[a] = tb;
				keys[b] = ta;
				tb = default(IntPtr);
			}
			if (q != b && comparer.Compare(tq = tq != IntPtr.Zero ? tq : keys[q], tb = tb != IntPtr.Zero ? tb : keys[b]) > 0x0)
			{
				keys[q] = tb;
				keys[b] = tq;
			}
		}

		static public unsafe void qsort(IntPtr* arr, int left, int right, IComparer<IntPtr> cmp)
		{
			do
			{
				int a = left, b = right, mid = a + ((b - a) >> 0x1);
#if swapper
				swapper(arr, cmp, a, b, mid);
#else
				swap_if(keys, cmp, a, mid);
				swap_if(keys, cmp, a, b);
				swap_if(keys, cmp, mid, b);
#endif
				IntPtr y = arr[mid];
				do
				{
					IntPtr ta;
					while ((ta = arr[a]) != y && cmp.Compare(ta, y) < 0x0)
						a++;
					IntPtr tb = a == b ? ta : arr[b];
					while (tb != y && cmp.Compare(y, tb) < 0x0)
						tb = arr[--b];

					if (a > b)
						break;
					if (a < b)
					{
						arr[a] = tb;
						arr[b] = ta;
					}
					a++;
					b--;
				}
				while (a <= b);

				if ((b - left) <= (right - a))
				{
					if (left < b)
						qsort(arr, left, b, cmp);
					left = a;
				}
				else
				{
					if (a < right)
						qsort(arr, a, right, cmp);
					right = b;
				}
			}
			while (left < right);
		}
	};
}
